//松弛操作
//ralaxation

//松弛操作是图论中最短路径类算法的核心技术

//图的已知信息是节点下标号和权值 边的下标号 方向和权值
//以及节点与边的对应关系 这些信息足以用于计算图论中所有问题
//
//三角形定理:
//考虑图中a b c三个节点 ab相连 bc相连 ac不相连
//			b
//		/		\
//	a				c
//已知从b到a的最短距离dist[b] 但不知道从c到a的最短距离dist[c]
//对于这样不相连的两节点c和a 将其最短距离初始化为极大值INF
//即dist[c]=INF 但我们知道bc之间的距离|bc|
//在三角形abc中永远有: |ac|<|ab|+|bc| 松弛操作借鉴了这个性质
//即若已知的|ac|>|ab|+|bc| 则可以将|ac|更新为|ac|=|ab|+|bc|
//
//路径标记技术:
//最短路径算法还使用了路径标记技术 设置数组path记录最短路径
//将起点beg看作最短路径的根节点 则路径上相邻两节点中离beg近的是离beg远的的父节点
//用path[i]指代节点i在最短路径上的父节点下标号
//该技术在生成树 最短路径 最大流和二分匹配等问题中都有使用
//在图论中是一项基础但却应用广泛的技术 拥有重要地位
//
//松弛操作:
//if (dist[c] > dist[b] + |bc|)
//{
//	dist[c] = dist[b] + |bc|;
//	path[c] = b;
//}

//void relaxation(graph_matrix& g);
